package com.wangbo.basic.circular;

import lombok.Data;

/**
 * 环形链表
 */
@Data
public class CircularLinkedList<T> {

    private Node<T> first; // 环首指针，指向链表入口

    public CircularLinkedList() {
    }

    /**
     * 添加节点
     **/
    public void add(T data) {
        Node<T> newNode = new Node<>(data);
        if (first == null) {
            first = newNode;
            first.setNext(newNode); // 自环
        } else {
            Node<T> last = getLast();
            last.setNext(newNode);
            newNode.setNext(first);
        }
    }

    /**
     * 获取环尾
     **/
    public Node<T> getLast() {
        // 空链表
        if (isEmpty())
            return null;
        // 非空链表
        Node<T> last = first;
        while (last.getNext() != first) {
            last = last.getNext();
        }
        return last;
    }

    /**
     * 遍历显示
     **/
    public void show() {
        if (first == null)
            System.out.println("[]");
        Node<T> current = first;
        while (current.getNext() != first) {
            System.out.println(current);
            current = current.getNext();
        }
        System.out.println(current);
    }

    /**
     * 移除从 first 数起第n个环上的节点
     * 用于解决约瑟夫问题
     **/
    public Node<T> remove(int n) {
        // 空队列
        if (isEmpty() || n < 1) {
            return null;
        }

        // 单一节点队列
        if (first.getNext() == first) {
            Node<T> temp = first;
            first = null;
            return temp;
        }

        // 多节点队列
        Node<T> last = getLast();
        for (int i = 1; i < n; i++) { // first从1数起
            last = first;
            first = first.getNext();
        }
        Node<T> temp = first;
        first = first.getNext();
        last.setNext(first);
        return temp;
    }

    /**
     * 是否为空
     **/
    public boolean isEmpty() {
        return first == null;
    }

}
